
"""
96. 不同的二叉搜索树
"""

class Solution:

    def __init__(self):
        # 表示[i,j]区间组成的树个数为nums[i, j]
        self.nums = [[]]

    def numTrees(self, n: int) -> int:
        """
         * 思路：1-n区间的数据组成不同的二叉树，由于二叉搜索树特性“左子树 < 根节点 < 右子树”，以每个元素作为根节点穷举出所有树，比如以i作为根节点，
         *      那么[1, i-1]和[i+1,n]分别为左右子树，本地结果就是[1, i-1]区间组成的值数个数 * [i+1,n]区间组成的值数个数
         * 做法：定义函数count(low, high)，表示区间[low, high]组成子树的个数
        """
        self.nums = [[0 for i in range(n + 1)] for i in range(n + 1)]
        return self.count(1, n)


    def count(self, low, high) -> int:
        """
        区间[low, high]组成子树的个数
        优化：定义一个二维数组nums[i, j]，表示[i,j]区间组成的树个数为nums[i, j]
        @param low: 下标
        @param high: 上标
        @return: 子树的个数
        """
        if low > high:
            return 1

        # 从数组中取
        if self.nums[low][high] != 0:
            return self.nums[low][high]

        res = 0
        for i in range(low, high+1):
            left = self.count(low, i - 1)
            right = self.count(i + 1, high)
            res = res + (left * right)

        # 存储
        self.nums[low][high] = res

        return res